package hwFive1;

import java.util.*;

public class KeyIndexSort {

    public static void sort(String[] a) {
        // 1. 统计每个键的频率
        Map<String, Integer> frequencyMap = new HashMap<>();
        for (String key : a) {
            frequencyMap.put(key, frequencyMap.getOrDefault(key, 0) + 1);
        }

        // 2. 按照键排序（需要有序输出时）
        List<String> keys = new ArrayList<>(frequencyMap.keySet());
        Collections.sort(keys);

        // 3. 计算每个键的起始索引
        Map<String, Integer> indexMap = new HashMap<>();
        int index = 0;
        for (String key : keys) {
            indexMap.put(key, index);
            index += frequencyMap.get(key);
        }

        // 4. 创建结果数组并排序
        String[] result = new String[a.length];
        for (String key : a) {
            int position = indexMap.get(key);
            result[position] = key;
            indexMap.put(key, position + 1); // 更新索引
        }

        // 5. 将排序后的结果复制回原数组
        System.arraycopy(result, 0, a, 0, a.length);
    }

    // 测试代码
    public static void main(String[] args) {
        String[] a = { "banana", "apple", "orange", "banana", "apple", "banana" };
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
